1. Field of the Invention
The present invention relates to packet forwarding. More particularly, the present invention relates to forwarding packets through manipulating multiple queues of packets.
2. Description of the Related Art
Routers are commonly used to forward packets within a network. Routers typically include a CPU, a memory, and a plurality of inbound and outbound ports. Typically, data is received at an inbound port as a packet. When a packet is received at an inbound port, it is ultimately filtered or forwarded via an outbound port.
FIG. 1 is a block diagram illustrating a conventional router 102. Rather than sending each packet as it is received at an inbound port 104-1, 104-2, packets are typically stored in a single inbound queue 106-1, 106-2 via a hardware inbound interface, or “controller,” associated with the corresponding inbound port 104-1, 104-2. When the CPU wakes up, it obtains a packet from the inbound queue 104-1, 104-2 classifies, and transfers the packet to a hardware outbound interface, or “controller.” The hardware outbound interface then stores the packet in an outbound queue 108-1, 108-2 associated with an outbound port 110-1, 110-2. Transferring may be accomplished through moving the packet or simply modifying a pointer to the packet. The outbound interface then forwards the packet. Typically, this is performed for each packet.
In order to send each packet stored in the inbound queue, the packets must be transferred to the appropriate outbound queue. Often, each peripheral interface is designed for use with a particular protocol (e.g., Ethernet) and therefore a particular representation, or data structure. Thus, the inbound interface and the outbound interface often have incompatible data structures. By way of example, queue descriptions for the inbound interface and the outbound interface often have different formats. Thus, the CPU must translate the packets stored in the inbound queue to an outbound representation compatible with the outbound interface. The packet is then transferred to an outbound queue associated with an outbound port. Accordingly, it would be desirable if the inbound interface and the outbound interface could be designed to provide compatible data structures, thereby facilitating the transfer of data between the inbound and the outbound controller.
Inbound controllers typically store packets as they are received in a single inbound queue. FIG. 2 is a block diagram illustrating a router having a conventional inbound and outbound controller. As shown, data 202 is received by an inbound controller 204. The inbound controller 204 then stores this data 202 (e.g., packet) in memory 206 in an inbound queue 208. The inbound queue 208 includes a plurality of queue entries 210 corresponding to a plurality of packets. By way of example, each one of the plurality of packets may be stored in a packet buffer 212. In order to forward each packet stored in the inbound queue 208, the CPU must transfer each entry 210 in the inbound queue 208 to an outbound queue 214 associated with an outbound controller 216. The outbound queue 214 similarly includes a plurality of queue entries 218 corresponding to a plurality of packets. Thus, an entry 210 in the inbound queue 208 may be transferred to the outbound queue 214 through modifying a pointer to a packet buffer 220 associated with an entry being transferred.
Since each packet is individually transferred from the inbound controller to the outbound controller, this produces a substantial burden on the CPU and a low packet per second forwarding rate. By way of example, each queue entry in both the inbound and the outbound queues may include a packet descriptor and a pointer to a packet buffer that holds data for the packet. Thus, transferring a single packet may require that a pointer to the transferred packet be added to the outbound queue as well as removed from the inbound queue. In addition, any packet descriptors must similarly be transferred. Since the transfer of each packet requires that several steps be performed, the burden on the CPU is substantial. Thus, it would be desirable if an inbound interface for a router could be designed which would reduce this burden on the CPU while maximizing the packet per second forwarding rate. Accordingly, it would be beneficial if entire queues could be transferred between the inbound controller and the outbound controller rather than individual packets, thereby increasing the throughput of a router.
Classification of packets similarly increases the burden on the CPU. While inbound controllers and outbound controllers are typically implemented in hardware, classification of packets is typically performed in software. Thus, numerous CPU cycles are commonly dedicated to such classification. Accordingly, it would be beneficial if an inbound interface could be implemented in hardware such that each inbound packet were sorted into an inbound queue corresponding sorting criteria such as the source address and the destination address of the packet.
Once each packet is sent by the outbound controller, the CPU often deallocates the corresponding packet buffer. Thus, this deallocation is typically performed for each packet individually. However, it would be beneficial if the memory could be deallocated and reused in a more efficient manner. Accordingly, it would be desirable if an outbound interface for a router could be designed which would reduce the number of CPU cycles dedicated to the deallocation of these buffers.
In addition to dedicating numerous CPU cycles to transferring packets between an inbound controller and an outbound controller, classifying packets, and deallocating packet buffers associated with the packets, these packet buffers typically consume a considerable amount of memory. A packet buffer is typically preallocated for each entry in an inbound queue. Since all of these packet buffers may not be utilized consistently, a portion of these dedicated buffers often remain unused. Accordingly, it would be desirable to reduce the amount of memory required and therefore the production costs associated with each router.